package com.moyoutian.leetcode;


import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * 给你一个包含 n 个整数的数组nums，判断nums中是否存在三个元素 a，b，c ，使得a + b + c = 0 ？请你找出所有和为 0 且不重复的三元组。
 * <p>
 * 注意：答案中不可以包含重复的三元组。
 * <p>
 * <p>
 * <p>
 * 示例 1：
 * <p>
 * 输入：nums = [-1,0,1,2,-1,-4]
 * 输出：[[-1,-1,2],[-1,0,1]]
 * 示例 2：
 * <p>
 * 输入：nums = []
 * 输出：[]
 * 示例 3：
 * <p>
 * 输入：nums = [0]
 * 输出：[]
 * <p>
 * <p>
 * 提示：
 * <p>
 * 0 <= nums.length <= 3000
 * -105 <= nums[i] <= 105
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/3sum
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 *
 * @author gaoxiang
 */
public class Demo15 {

    public static void main(String[] args) {
        final int[] intAr = new int[]{-1,0,1,2,-1,-4};
        threeSum(intAr);
    }


    /**
     * 解题思路
     * 因为和为0 所以 x=-x
     * <p>
     * 所以数据应该分布在0的两侧x=-x，或者全部是0。
     * 现在有三个数据 x,y,z 假设其中有两个数字为0，那么第三个数字肯定为0。假设有一个数字为(z=0)，那么 x=-y。假设没有数字为0 ，那么x+y=-z
     *
     * @param nums
     */

    public static List<List<Integer>> threeSum(int[] nums) {
        if (nums.length < 3) {
            return new ArrayList<>();
        }
        List<List<Integer>> list = new ArrayList<>();
        Map<Integer, Integer> leftMap = new HashMap<>();
        Map<Integer, Integer> rightMap = new HashMap<>();
        Map<String, Integer> keyMap = new HashMap<>();
        int lLen = sw(nums, leftMap, rightMap);
        if (lLen == -1) {
            return list;
        }
        lLen = lLen;
        if (leftMap.size() > 0 && rightMap.size() > 0) {
            // 双负数找一正数
            for (int l = 0; l < lLen; l++) {
                for (int ll = l + 1; ll < lLen; ll++) {
                    int l1 = nums[l], l2 = nums[ll];
                    int tempX = -(l1 + l2);
                    if (rightMap.get(tempX) != null) {
                        String key = getKey(l1, l2, tempX);
                        if (keyMap.get(key) == null) {
                            list.add(getToList(l1, l2, tempX));
                            keyMap.put(key, keyMap.getOrDefault(key, 0) + 1);
                        }
                    }
                }
            }
            // 双正数找一付数
            for (int l = lLen; l < nums.length; l++) {
                for (int ll = l + 1; ll < nums.length; ll++) {
                    int l1 = nums[l], l2 = nums[ll];
                    int tempX = -(l1 + l2);
                    if (leftMap.get(tempX) != null) {
                        String key = getKey(l1, l2, tempX);
                        if (keyMap.get(key) == null) {
                            list.add(getToList(l1, l2, tempX));
                            keyMap.put(key, keyMap.getOrDefault(key, 0) + 1);
                        }
                    }
                }
            }
        }

        if (rightMap.getOrDefault(0, 0) >= 3) {
            String key = getKey(0, 0, 0);
            if (keyMap.get(key) == null) {
                list.add(getToList(0, 0, 0));
                keyMap.put(key, keyMap.getOrDefault(key, 0) + 1);
            }
        }
        return list;
    }

    public static List<Integer> getToList(int x, int y, int z) {
        List<Integer> tempList = new ArrayList<>();
        tempList.add(x);
        tempList.add(y);
        tempList.add(z);
        return tempList;
    }

    /**
     * 排序取key
     */
    public static String getKey(int x, int y, int z) {
        String keys;
        if (x < y) {
            if (y < z) {
                keys = x + "_" + y + "_" + z;
            } else {
                if (x > z) {
                    keys = z + "_" + x + "_" + y;
                } else {
                    keys = x + "_" + z + "_" + y;
                }
            }
        } else {
            if (z < y) {
                keys = z + "_" + y + "_" + x;
            } else {
                if (x > z) {
                    keys = y + "_" + z + "_" + x;
                } else {
                    keys = y + "_" + x + "_" + z;
                }
            }
        }
        return keys;
    }


    /**
     * 用0将数组分割成两半
     *
     * @param nums 0-没有0，正负不全,1-有0正负全,2-没有0，正负数全，3-没有0正负不全
     */
    public static int sw(int[] nums, Map<Integer, Integer> leftMap, Map<Integer, Integer> rightMap) {
        if (nums != null && nums.length > 1) {
            int temp = 0;
            int left = 0;
            int returnNumber = 0;
            int right = nums.length - 1;
            while (left < right) {
                while (nums[left] < temp && left < right) {
                    leftMap.merge(nums[left], 1, Integer::sum);
                    left++;
                    returnNumber++;
                }
                while (nums[right] >= temp && left < right) {
                    rightMap.merge(nums[right], 1, Integer::sum);
                    right--;
                }
                swap(nums, left, right);
            }
            rightMap.merge(nums[right], 1, Integer::sum);

            right = nums.length - 1;
            while (left < right) {
                while (nums[left] <= temp && left < right) {
                    left++;
                }
                while (nums[right] > temp && left < right) {
                    right--;
                }
                swap(nums, left, right);
            }

            return returnNumber;
        }
        return -1;
    }


    public static void swap(int[] ints, int i, int j) {
        int c = ints[i];
        ints[i] = ints[j];
        ints[j] = c;
    }
}


